package com.fengye.algorithms.leecode;

import java.util.Scanner;

/**
 * @Author fengye
 * @Date 2023/3/10 10:09
 **/
public class BigNumberMulti43 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String num1 = in.next();
            String num2 = in.next();
            System.out.println(multiply2(num1, num2));
            //System.out.println(sub("765", "558"));
        }
    }

    /**
     * 乘完就处理进位
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1,String num2) {
        char[] chs1 = num1.toCharArray();
        char[] chs2 = num2.toCharArray();
        //int n = chs1.length>chs2.length ? chs1.length:chs2.length;

        //List<String> list = new ArrayList<>();
        String result = "";
        for(int i=chs2.length-1;i>=0;i--) {
            int t = 0;
            StringBuilder sb = new StringBuilder();
            for(int j=chs1.length-1;j>=0;j--) {
                int a = chs1[j] - '0';
                int b = chs2[i] - '0';
                int num = a * b + t;
                if(num < 10) {
                    sb.append(num);
                    t=0;
                } else {
                    char[] tc = (num+"").toCharArray();
                    sb.append(tc[1]);
                    t = tc[0] - '0';
                }
            }
            if(t > 0) {
                sb.append(t);
            }
            String ts = sb.reverse().toString();
            for(int n = 0; n < (chs2.length-1-i);n++) {
                ts += "0";
            }

            if((chs2.length-1-i)==0) {
                result = ts;
            } else {
                result = add(result, ts);
            }
        }
        return result;
    }

    /**
     * 乘完再处理进位
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply3(String num1, String num2) {

        if(num1.equals("0")||num2.equals("0")) {
            return "0";
        }

        int len1=num1.length(), len2=num2.length();
        int[] ansArr=new int[len1+len2];
        for(int i=len1-1;i>=0;i--){
            int x=num1.charAt(i)-'0';
            for(int j=len2-1;j>=0;j--){
                int y=num2.charAt(j)-'0';
                ansArr[i+j+1]+=x*y;
            }
        }

        for(int i=len1+len2-1;i>0;i--){
            ansArr[i-1]+=ansArr[i]/10;
            ansArr[i]=ansArr[i]%10;
        }

        StringBuilder ans=new StringBuilder();
        int index= ansArr[0] == 0? 1:0;
        while(index<len1+len2){
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }

    /**
     * karatsuba 只适用两个大数乘法
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply2(String num1, String num2) {
        String kNum1 = num1;
        String kNum2 = num2;

        int max = num1.length();
        if(num1.length() > num2.length()) {
            for(int i=0;i<num1.length()-num2.length();i++) {
                kNum2 = "0" + kNum2;
            }
        } else if(num1.length() < num2.length()){
            for(int i=0;i<num2.length()-num1.length();i++) {
                kNum1 = "0" + kNum1;
            }
        }
        String result = karatsuba(kNum1,kNum2);
        for(int i=0;i<result.length(); i++){
            if(result.charAt(i) != '0') {
                result = result.substring(i);
                break;
            }
        }
        return result;
    }

    public static String karatsuba(String num1, String num2) {
        if(num1.length() <= 2 || num2.length() <= 2) {
            return (Integer.parseInt(num1) * Integer.parseInt(num2)) + "";
        }

        int size1 = num1.length();
        int size2 = num2.length();
        int half = Math.min(size1, size2) / 2;

        String a = num1.substring(0,size1-half);
        String b = num1.substring(size1-half);
        String c = num2.substring(0, size2 - half);
        String d = num2.substring(size2 - half);

        String z0 = karatsuba(a, c);
        String z1 = karatsuba(b, d);
        String z2 = sub(karatsuba(add(a , b), add(c , d)) , add(z0 , z1));
        StringBuilder z0Sb = new StringBuilder(z0);
        for (int i = 1; i <= 2*half;i++) {
            z0Sb.append("0");
        }
        StringBuilder z2Sb = new StringBuilder(z2);
        for (int i = 1; i <=half;i++) {
            z2Sb.append("0");
        }

        return add(z0Sb.toString(),add(z2Sb.toString(), z1));
    }

    /**
     * 大数减法
     * @param aStr
     * @param bStr
     * @return
     */
    public static String sub(String aStr, String bStr) {
        char[] aCh = new StringBuilder(aStr).reverse().toString().toCharArray();
        char[] bCh = new StringBuilder(bStr).reverse().toString().toCharArray();
        // 必须算出a和b大小
        boolean bBig = false;
        if(aCh.length < bCh.length) {
            bBig = true;
        } else if (aCh.length == bCh.length) {
            for(int i = bCh.length-1; i >= 0 ;i--) {
                if (bCh[i] > aCh[i]) {
                    bBig = true;
                    break;
                } else if(aCh[i] > bCh[i]) {
                    break;
                }
            }
        }

        int n = !bBig ? aCh.length : bCh.length;
        int t = 0;
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++) {
            // 保证都是大的减小的
            int a = i<aCh.length ? aCh[i] - '0': 0;
            int b = i <bCh.length ? bCh[i] - '0': 0;
            if(bBig) {
                b = i<aCh.length ? aCh[i] - '0': 0;
                a = i <bCh.length ? bCh[i] - '0': 0;
            }
            if(t == 1) {
                a -= 1;
            }
            if(a >= b) {
                sb.append(a-b);
                t = 0;
            } else {
                if(i+1 < aCh.length) {
                    sb.append(a + 10 - b);
                    t = 1;
                } else {
                    sb.append(b - a);
                     t=0;
                }
            }
        }

        if(bBig) {
            sb.append("-");
        }
        return sb.reverse().toString();
    }

    /**
     * 大数加法
     * @param aStr
     * @param bStr
     * @return
     */
    public static String add(String aStr, String bStr) {
        char[] aCh = new StringBuilder(aStr).reverse().toString().toCharArray();
        char[] bCh = new StringBuilder(bStr).reverse().toString().toCharArray();

        int n = aCh.length > bCh.length ? aCh.length : bCh.length;
        int t = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n;i++) {
            int a = i<aCh.length ? aCh[i] - '0': 0;
            int b = i < bCh.length ? bCh[i] - '0': 0;
            int num = a + b + t;

            if(num < 10) {
                sb.append(num);
                t = 0;
            } else {
                char[] c = (num + "").toCharArray();
                sb.append(c[1]);
                t = c[0] - '0';
            }
        }
        if(t>0) {
            sb.append(t);
        }

        return sb.reverse().toString();
    }
}
